স্ট্যাক (Stack) এবং কিউ (Queue) হল দুটি মৌলিক ডেটা স্ট্রাকচার যা তথ্য সংরক্ষণ এবং পরিচালনার জন্য ব্যবহৃত হয়। এদের নিজস্ব বৈশিষ্ট্য, ব্যবহার এবং সময় জটিলতা রয়েছে। নিচে স্ট্যাক এবং কিউ সম্পর্কে বিস্তারিত আলোচনা করা হলো।
স্ট্যাক (Stack)
বিবরণ: স্ট্যাক একটি LIFO (Last In, First Out) ডেটা স্ট্রাকচার। এর মানে হল, শেষ প্রবেশ করা উপাদানটি প্রথমে বের হয়। স্ট্যাকটি একধরনের "পুঞ্জ" হিসেবে কাজ করে, যেখানে উপাদানগুলি একটির ওপর একটির মতো রাখা হয়।
বৈশিষ্ট্য:
- পুশ (Push): নতুন উপাদান স্ট্যাকে যুক্ত করা।
- পপ (Pop): সর্বশেষ উপাদানটি স্ট্যাক থেকে বের করা।
- পীক (Peek): সর্বশেষ উপাদানটি দেখতে কিন্তু মুছতে না।
সময় জটিলতা:
- পুশ: O(1)
- পপ: O(1)
- পীক: O(1)
ব্যবহার:
- ফাংশন কল ট্র্যাকিং: প্রোগ্রামে ফাংশন কলের গতিবিধি ট্র্যাক করার জন্য।
- অথentication ও আনঅথেনটিকেট: ফিরে যাওয়া এবং পুনর্বিবেচনা করার জন্য।
উদাহরণ (পাইথনে):
class Stack:
def __init__(self):
self.stack = []
def push(self, item):
self.stack.append(item)
def pop(self):
if not self.is_empty():
return self.stack.pop()
return None
def peek(self):
if not self.is_empty():
return self.stack[-1]
return None
def is_empty(self):
return len(self.stack) == 0
# ব্যবহার
s = Stack()
s.push(1)
s.push(2)
s.push(3)
print(s.pop()) # আউটপুট: 3
print(s.peek()) # আউটপুট: 2
কিউ (Queue)
বিবরণ: কিউ একটি FIFO (First In, First Out) ডেটা স্ট্রাকচার। এর মানে হল, প্রথমে প্রবেশ করা উপাদানটি প্রথমে বের হয়। কিউটি একধরনের "লাইন" বা "সার" হিসেবে কাজ করে, যেখানে উপাদানগুলি একটির পেছনে একটির মতো রাখা হয়।
বৈশিষ্ট্য:
- এনকিউ (Enqueue): নতুন উপাদান কিউতে যুক্ত করা।
- ডিকিউ (Dequeue): প্রথম উপাদানটি কিউ থেকে বের করা।
- ফ্রন্ট (Front): প্রথম উপাদানটি দেখতে কিন্তু মুছতে না।
সময় জটিলতা:
- এনকিউ: O(1)
- ডিকিউ: O(1)
- ফ্রন্ট: O(1)
ব্যবহার:
- কাস্টমার সার্ভিস: গ্রাহকদের সার্ভিস দেওয়ার জন্য।
- প্রিন্টার কিউ: প্রিন্টারগুলোর জন্য কাজের সারি তৈরি করতে।
উদাহরণ (পাইথনে):
class Queue:
def __init__(self):
self.queue = []
def enqueue(self, item):
self.queue.append(item)
def dequeue(self):
if not self.is_empty():
return self.queue.pop(0)
return None
def front(self):
if not self.is_empty():
return self.queue[0]
return None
def is_empty(self):
return len(self.queue) == 0
# ব্যবহার
q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue()) # আউটপুট: 1
print(q.front()) # আউটপুট: 2
উপসংহার
স্ট্যাক এবং কিউ হল দুটি মৌলিক ডেটা স্ট্রাকচার যা বিভিন্ন প্রোগ্রামিং সমস্যার সমাধানে ব্যবহৃত হয়। স্ট্যাক LIFO নীতিতে কাজ করে, যেখানে কিউ FIFO নীতিতে কাজ করে। এই ডেটা স্ট্রাকচারগুলি তাদের বিশেষ বৈশিষ্ট্যের কারণে বিভিন্ন বাস্তব জীবনের পরিস্থিতিতে গুরুত্বপূর্ণ। তাদের সঠিক ব্যবহার ডেটার কার্যকরী প্রবাহ এবং নিয়ন্ত্রণ নিশ্চিত করে।
স্ট্যাকের ধারণা
স্ট্যাক হলো একটি লাস্ট-ইন ফার্স্ট-আউট (LIFO - Last In, First Out) ডেটা স্ট্রাকচার, যেখানে সর্বশেষে যে উপাদানটি যোগ করা হয়, সেটিই প্রথমে সরানো হয়। স্ট্যাক সাধারণত একটি নির্দিষ্ট ক্রমে উপাদান সংরক্ষণ এবং ম্যানেজ করতে ব্যবহৃত হয়। স্ট্যাকের প্রধান ব্যবহারগুলো হলো রিকর্সিভ ফাংশন কল, ইউন্ডু অপারেশন, এবং ব্রাউজারে পেজের ব্যাক বাটন পরিচালনা।
স্ট্যাকের প্রধান অপারেশনগুলো
স্ট্যাকে সাধারণত তিনটি প্রধান অপারেশন থাকে:
- Push: স্ট্যাকে নতুন উপাদান যোগ করা।
- Pop: স্ট্যাক থেকে সর্বশেষ উপাদান সরানো।
- Peek (or Top): স্ট্যাকের শীর্ষে থাকা উপাদানটি দেখা, কিন্তু সরানো হয় না।
১. Push অপারেশন
Push অপারেশনের মাধ্যমে স্ট্যাকের শীর্ষে নতুন একটি উপাদান যোগ করা হয়। স্ট্যাকের সর্বশেষ উপাদানটি এভাবেই শীর্ষে থাকে। স্ট্যাকের আকার নির্দিষ্ট থাকলে এটি পূর্ণ (Full) হওয়া পর্যন্ত Push করা যায়।
ধাপসমূহ:
- নতুন উপাদান যোগ করার আগে চেক করুন যে স্ট্যাক পূর্ণ কিনা।
- স্ট্যাক পূর্ণ না হলে শীর্ষে উপাদান যোগ করুন।
উদাহরণ:
স্ট্যাক: [5, 10, 15]
Push(20)
স্ট্যাক: [5, 10, 15, 20]
২. Pop অপারেশন
Pop অপারেশনের মাধ্যমে স্ট্যাকের শীর্ষে থাকা উপাদানটি সরানো হয়। এটি এলIFO এর ভিত্তিতে কাজ করে, তাই সর্বশেষে যোগ করা উপাদানটি প্রথমে সরানো হয়। Pop অপারেশন প্রয়োগের আগে চেক করা উচিত যে স্ট্যাক ফাঁকা (Empty) আছে কিনা।
ধাপসমূহ:
- শীর্ষের উপাদান সরানোর আগে চেক করুন যে স্ট্যাক ফাঁকা কিনা।
- ফাঁকা না থাকলে শীর্ষের উপাদানটি সরিয়ে নিন।
উদাহরণ:
স্ট্যাক: [5, 10, 15, 20]
Pop()
স্ট্যাক: [5, 10, 15]
৩. Peek অপারেশন
Peek অপারেশনটি স্ট্যাকের শীর্ষে থাকা উপাদানটি দেখতে সাহায্য করে, তবে এটিকে সরানো হয় না। এটি স্ট্যাক ফাঁকা না থাকলে সর্বশেষ যোগ করা উপাদানটি প্রদর্শন করে।
ধাপসমূহ:
- শীর্ষে থাকা উপাদানটি দেখতে স্ট্যাক ফাঁকা কিনা চেক করুন।
- শীর্ষে থাকা উপাদানটি দেখান (কিন্তু সরাবেন না)।
উদাহরণ:
স্ট্যাক: [5, 10, 15, 20]
Peek()
আউটপুট: 20
স্ট্যাক: [5, 10, 15, 20] // উপাদান সরানো হয়নি
স্ট্যাক অপারেশনের উদাহরণ (Python কোড)
class Stack:
def __init__(self):
self.stack = []
# Push অপারেশন
def push(self, item):
self.stack.append(item)
# Pop অপারেশন
def pop(self):
if not self.is_empty():
return self.stack.pop()
else:
return "Stack is empty"
# Peek অপারেশন
def peek(self):
if not self.is_empty():
return self.stack[-1]
else:
return "Stack is empty"
# Stack ফাঁকা কিনা চেক করা
def is_empty(self):
return len(self.stack) == 0
# ব্যবহার
stack = Stack()
stack.push(10)
stack.push(20)
stack.push(30)
print("Peek:", stack.peek()) # আউটপুট: 30
print("Pop:", stack.pop()) # আউটপুট: 30
print("Pop:", stack.pop()) # আউটপুট: 20
print("Peek:", stack.peek()) # আউটপুট: 10
স্ট্যাকের ব্যবহার ক্ষেত্র
- ফাংশন কল স্ট্যাক: প্রোগ্রামে রিকার্সিভ ফাংশন কলগুলো স্ট্যাকের মাধ্যমে ম্যানেজ করা হয়।
- ব্রাউজার ব্যাক ফাংশন: ব্রাউজারের ব্যাক বাটন ক্লিকের ইতিহাস স্ট্যাকে সংরক্ষণ করা হয়।
- পোলিশ নোটেশন: ইনফিক্স, পোস্টফিক্স, এবং প্রিফিক্স এক্সপ্রেশন ম্যানেজ করার জন্য স্ট্যাক ব্যবহৃত হয়।
- ইউন্ডু অপারেশন: কোনো প্রোগ্রামে পূর্বের অবস্থায় ফিরে যাওয়ার জন্য স্ট্যাক ব্যবহৃত হয়।
উপসংহার
স্ট্যাক একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা LIFO ভিত্তিতে কাজ করে। এটি বিভিন্ন ধরনের সমস্যায় কার্যকরী সমাধান দেয়, যেমন ফাংশন কল স্ট্যাক, ইউন্ডু অপারেশন, এবং ইনফিক্স-টু-পোস্টফিক্স রূপান্তর। Push, Pop, এবং Peek অপারেশন স্ট্যাক ব্যবহারের জন্য প্রয়োজনীয় এবং কার্যকরী ভূমিকা পালন করে।
কিউ (Queue) হল একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা FIFO (First In, First Out) পদ্ধতির ভিত্তিতে কাজ করে। এর মানে হলো যে উপাদানটি প্রথমে কিউতে যোগ করা হয়, সেটি প্রথমে বের হবে। কিউ সাধারণত দৈনিক জীবনে ব্যবহৃত অনেক সিস্টেমে দেখা যায়, যেমন সার্ভিস ডেস্কে, প্রিন্টার ম্যানেজমেন্টে এবং আরও অনেক ক্ষেত্রে।
কিউয়ের মৌলিক ধারণা
কিউ একটি আবদ্ধ ডেটা স্ট্রাকচার, যা দুটি প্রধান অপারেশন ব্যবহার করে: Enqueue এবং Dequeue। এছাড়াও, কিউয়ের শীর্ষ এবং তল অর্থাৎ প্রথম এবং শেষ উপাদান সংক্রান্ত কিছু অপারেশন থাকে।
কিউয়ের অপারেশন
১. Enqueue:
- নতুন উপাদান কিউতে যোগ করার প্রক্রিয়া। এটি কিউয়ের শেষে নতুন উপাদান যুক্ত করে।
- টাইপ: O(1) সময় জটিলতা।
২. Dequeue:
- কিউ থেকে প্রথম উপাদান মুছে ফেলার প্রক্রিয়া। এটি কিউয়ের শুরু থেকে উপাদানটি বের করে এবং মুছে দেয়।
- টাইপ: O(1) সময় জটিলতা।
৩. Front:
- কিউয়ের প্রথম উপাদানটি দেখতে পাওয়ার প্রক্রিয়া। এটি কেবল প্রথম উপাদানটি রিটার্ন করে কিন্তু এটি মুছে দেয় না।
- টাইপ: O(1) সময় জটিলতা।
৪. Rear:
- কিউয়ের শেষ উপাদানটি দেখতে পাওয়ার প্রক্রিয়া। এটি কেবল শেষ উপাদানটি রিটার্ন করে কিন্তু এটি মুছে দেয় না।
- টাইপ: O(1) সময় জটিলতা।
উদাহরণ: কিউ ব্যবহার
এখন একটি সম্পূর্ণ উদাহরণ দিয়ে কিউয়ের অপারেশনগুলো বোঝা যাক:
from collections import deque
class Queue:
def __init__(self):
self.queue = deque()
def enqueue(self, item):
self.queue.append(item) # Enqueue
def dequeue(self):
if not self.is_empty():
return self.queue.popleft() # Dequeue
return None
def front(self):
if not self.is_empty():
return self.queue[0] # Front
return None
def rear(self):
if not self.is_empty():
return self.queue[-1] # Rear
return None
def is_empty(self):
return len(self.queue) == 0
def size(self):
return len(self.queue)
# ব্যবহার
my_queue = Queue()
my_queue.enqueue(10)
my_queue.enqueue(20)
my_queue.enqueue(30)
print("Front element:", my_queue.front()) # 10
print("Rear element:", my_queue.rear()) # 30
print("Dequeue element:", my_queue.dequeue()) # 10
print("New front element:", my_queue.front()) # 20
print("Queue size:", my_queue.size()) # 2
উপসংহার
কিউ একটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা FIFO পদ্ধতির উপর কাজ করে। এর বিভিন্ন অপারেশন যেমন Enqueue, Dequeue, Front, এবং Rear ডেটা ব্যবস্থাপনায় কার্যকরী ভূমিকা পালন করে। কিউ ব্যবহৃত হয় বিভিন্ন বাস্তব জগতের সমস্যা সমাধানে, যেমন সার্ভিস ডিস্ক, প্রিন্টার ম্যানেজমেন্ট, এবং অনেক অ্যাপ্লিকেশনে।
স্ট্যাক ও কিউ এর ব্যবহার
স্ট্যাক এবং কিউ হল দুইটি মৌলিক ডেটা স্ট্রাকচার যা বিভিন্ন কাজের জন্য ব্যবহৃত হয়। এই দুটি ডেটা স্ট্রাকচারগুলি বিশেষ করে সমস্যাগুলির সমাধানে কার্যকরী। নিচে স্ট্যাক এবং কিউ এর দুটি গুরুত্বপূর্ণ ব্যবহার নিয়ে আলোচনা করা হলো: ব্যালেন্সড প্যারেনথেসিস এবং ইনফিক্স থেকে পোস্টফিক্স কনভার্সন।
১. ব্যালেন্সড প্যারেনথেসিস (Balanced Parentheses)
ব্যালেন্সড প্যারেনথেসিস সমস্যা হল চিহ্নগুলির একটি সিকোয়েন্স যা সঠিকভাবে বন্ধ হয় কিনা তা যাচাই করার প্রক্রিয়া। উদাহরণস্বরূপ, "(())" একটি ব্যালেন্সড প্যারেনথেসিস, কিন্তু "(()" একটি ব্যালেন্সড নয়।
স্ট্যাক ব্যবহার করে ব্যালেন্সড প্যারেনথেসিস যাচাই:
def is_balanced(expression):
stack = []
opening = {'(': ')', '{': '}', '[': ']'}
for char in expression:
if char in opening:
stack.append(char)
elif char in opening.values():
if not stack or opening[stack.pop()] != char:
return False
return not stack
# পরীক্ষা করা
expression1 = "((()))"
expression2 = "(()"
print(is_balanced(expression1)) # Output: True
print(is_balanced(expression2)) # Output: False
২. ইনফিক্স থেকে পোস্টফিক্স কনভার্সন (Infix to Postfix Conversion)
ইনফিক্স পদ্ধতিতে অপারেটরগুলি অপার্যান্ডগুলির মধ্যে থাকে (যেমন A + B), কিন্তু পোস্টফিক্স পদ্ধতিতে অপারেটরগুলি তাদের অপার্যান্ডগুলির পরে থাকে (যেমন A B +)। স্ট্যাক ব্যবহার করে ইনফিক্সকে পোস্টফিক্সে রূপান্তর করা হয়।
ইনফিক্স থেকে পোস্টফিক্স রূপান্তরের অ্যালগরিদম:
- একটি স্ট্যাক তৈরি করুন।
- ইনফিক্স অভিব্যক্তির প্রতিটি চিহ্ন পরীক্ষা করুন:
- যদি এটি একটি অপার্যান্ড (যেমন সংখ্যা বা ভেরিয়েবল) হয়, তবে এটি আউটপুটে যুক্ত করুন।
- যদি এটি একটি ওপেনিং প্যারেন্টিসিস হয়, তবে স্ট্যাকে যুক্ত করুন।
- যদি এটি একটি ক্লোজিং প্যারেন্টিসিস হয়, তবে স্ট্যাক থেকে ওপেনিং প্যারেন্টিসিস পর্যন্ত অপারেটরগুলি বের করুন এবং আউটপুটে যুক্ত করুন।
- যদি এটি একটি অপারেটর হয়, তবে প্রিওরিটি অনুযায়ী স্ট্যাক থেকে অপারেটরগুলি বের করুন এবং তাদের আউটপুটে যুক্ত করুন, তারপর বর্তমান অপারেটরটি স্ট্যাকে যুক্ত করুন।
- সমস্ত ইনপুট প্রক্রিয়া হওয়ার পরে, স্ট্যাক থেকে সমস্ত অপারেটর বের করে আউটপুটে যুক্ত করুন।
ইনফিক্স থেকে পোস্টফিক্স রূপান্তর কোড (Python):
def precedence(op):
if op == '+' or op == '-':
return 1
if op == '*' or op == '/':
return 2
return 0
def infix_to_postfix(expression):
stack = []
output = []
for char in expression:
if char.isalnum(): # Operand
output.append(char)
elif char == '(':
stack.append(char)
elif char == ')':
while stack and stack[-1] != '(':
output.append(stack.pop())
stack.pop() # Remove '(' from stack
else: # Operator
while (stack and precedence(stack[-1]) >= precedence(char)):
output.append(stack.pop())
stack.append(char)
while stack:
output.append(stack.pop())
return ''.join(output)
# পরীক্ষা করা
infix_expression = "A+B*(C^D-E)"
postfix_expression = infix_to_postfix(infix_expression)
print(f"Infix: {infix_expression} -> Postfix: {postfix_expression}")
উপসংহার
স্ট্যাক এবং কিউ হল দুটি গুরুত্বপূর্ণ ডেটা স্ট্রাকচার যা বিভিন্ন সমস্যার সমাধানে ব্যবহৃত হয়। ব্যালেন্সড প্যারেনথেসিস যাচাই এবং ইনফিক্স থেকে পোস্টফিক্স রূপান্তর করা দুইটি উদাহরণ। এই প্রযুক্তিগুলি প্রোগ্রামিংয়ে বিভিন্ন সমস্যার সমাধানে কার্যকর এবং দক্ষতা বৃদ্ধি করতে সাহায্য করে।
Read more
